#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](vector<int>& a1, vector<int>& a2) {return a1[0] < a2[0]||(a1[0]==a2[0]&&a1[1]>a2[1]); });
        vector<int> ans;
        for (auto& e : envelopes) {
            if (ans.size() == 0)
                ans.push_back(e[1]);
            else {
                int left = 0, right = ans.size() - 1;
                int now = e[1];
                if (now > ans.back()) {
                    ans.push_back(now);
                    continue;
                }
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (ans[mid] < now)
                        left = mid + 1;
                    else
                        right = mid;
                }
                ans[left] = now;
            }
        }
        return ans.size();
    }
};